A portion of the disclosure of this patent document contains material to which a claim of copyright protection is made. The owner has no objection to the facsimile reproduction of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.
1. Field of the Invention
This invention relates generally to numerical processing and more particularly to the field of floating-point number processing. More specifically, the invention relates to an apparatus and method for an exponential/logarithmic (E/L) general-purpose computational system based on particularly efficient fixed-point (FXP) generators of exponential and logarithmic functions in combination with a completely logarithmic data format. By comparison, a prior-art conventional floating-point (C-FLP) system is based on a FXP multiplier component and employs a partially or incompletely exponential/logarithmic data format.
2. Description of the State of the Art
There has been a paucity of actually working logarithmic data processors, and even fewer which have been used commercially, and virtually none for general-purpose use. Certain problems involved in the use or implementation of logarithmic processors are believed to have either not yet been recognized or not yet solved.
Prior art general-purpose logarithm evaluation, as compared with additions and subtractions and multiplications, have been inefficient and expensive--so much so that the inefficiency and expense are widely regarded as inevitable penalties on the logarithm operation itself. For example, a commercial C-FLP processor might execute logarithmic operations ten to twenty times slower than its relatively expensive multiplication operation.
Moreover, C-FLP systems seem to obey no recursive pattern for extending numerical precision. A popular conjecture among theorists holds that for arbitrarily high precision there is no fixed polynomial of the value of the first n digits of log x which can predict the value of the (n+1)-th digit with a probability greater than one half. Even if this conjecture is eventually proven, then the constraints which this would place on the construction of general-purpose logarithmic generators is more apparent than real for at least the following three important reasons: First, general-purpose logarithmic generators of even quite high fixed precision are, nevertheless, not of arbitrarily high precision. Second, limiting consideration to the first n digits of only the single function log x is a somewhat arbitrary and often unacknowledged restriction. Third, the polynomial form provides quiet compliance with the de facto dogma of C-FLP analysis whose tenets include: a) there is only one possible form of practical floating-point processor, b) the primitive economical operations of its "arithmetic" are restricted to the operations of addition, subtraction, and multiplication (with division not always quite included), and c) the multiplication operation is of a particular fixed degree of precision.
The conventional C-FLP multiplication operation is more expensive than the C-FLP addition or subtraction operations. Thus the minimax polynomial, which generally minimizes the required quantity of such multiplications, has become the mainstay of functional approximation for optimal C-FLP evaluation. To a certain extent, such polynomials also minimize the quantity of additions which is the more important consideration in E-FLP, as hereinafter explained.
A C-FLP computing environment usually contains such facilities as a library of scientific functions and a set of data conversions for interfacing with other data types. The appropriate correlatives of these facilities are also needed in an E-FLP computing environment, as hereinafter explained.
However, C-FLP computation was introduced almost four decades ago and met immediate and widespread acceptance. Designers of C-FLP processors made them easy to use. Confirmation of their skill can be found in the fact that entire generations of C-FLP users have been able to remain largely unaware of how a C-FLP processor actually works. The first such processors were implemented in software with multiplication speed suffering severely. The search for faster multiplication continued for decades. Hardware multipliers were investigated, but in many applications they were found to be too expensive to be of wide practical value.
The designers of the early processors were aware that so-called "logarithmic" arithmetic would be substantially equivalent to C-FLP arithmetic and that it would provide the ultimate in performance for floating-point multiplication: the floating-point multiplication would then be effected by the ultrarapid fixed-point addition. On the other hand, "logarithmic" addition and subtraction would correspond to intractable scientific library functions for which the impossibility of efficient generation was deemed obvious. Therefore, this development path was not pursued.
Many C-FLP processor designers since those early times have been of the opinion that the obstacles to efficient general-purpose "logarithmic" computation are inherent and unavoidable. This view is consistent with the fact that there has been no prior art account of any attempt to construct a processor capable of highly efficient general-purpose "logarithmic" computation.
In a specialized area of digital computation, N. G. Kingsbury and P. J. W. Rayner, in "Digital Filtering Using Logarithmic Arithmetic," Electronic Letters, Jan. 28, 1971, 56-58, proposed applying logarithmic arithmetic to digital filtering calculations. They proposed a processor using direct table look-up. Their processor necessarily had both its precision and its dynamic range severely restricted.
Exemplary early applications of logarithmic computation as are follows: A digital flow computer in U.S. Pat. No. 3,099,742 to Byrne, et al. in 1963; Calculating apparatus in U.S. Pat. No. 3,402,285 to Wang in 1968; and Digital Log Computer in U.S. Pat. No. 3,436,533 to Moore, et al. in 1969.
More recently, in "Integrated-Circuit Logarithmic Arithmetic Units," IEEE Computer Transactions, May 5, 1985, 475-483, J. H. Lang et al. have constructed a hardware logarithmic processor using direct table look-up. This processor possesses the equivalent of only 3.844 range bits and only 5.156 bits of precision, i.e., only 4.156 bits of mantissa. Lang et al. also include a comprehensive bibliography of the investigations of logarithmic arithmetic from the time of Kingsbury and Rayner up to 1985. All such prior art processors are based on direct table look-up using look-up indices which are substantially as large as the corresponding data-format value. The associated comparatively large table expense prohibits their use in all but the most highly specialized applications allowing very small data formats. Even here, particularly attentive experts are required in order to rigorously justify the use of arithmetic possessing such meager levels of precision and dynamic range. Casual general-purpose use is entirely out of the question.
Still more recently, in "A 20-Bit Logarithmic Number Processor," IEEE Computer Transactions, February 1988, 190-200, F. J. Taylor et al. have designed a hardware logarithmic processor performing the six operations: addition, subtraction, multiplication, division, square, and square root. The particular direct look-up of table values is modified only to the extent of selection among a few direct look-ups to tables having successively fewer bits of output but still with comparatively large numbers of bits of input which severely restricts precision and economy. The 12-bit mantissa with 7 bits of dynamic range provide levels of precision and dynamic range that would be adequate for a much wider range of practical applications if the processor also provided the logarithmic and exponential operations required for easy interface with C-FLP and FXP data associated with such equipment as analog-to-digital and digital-to-analog data converters. T. Stouraitis and F. J. Taylor analyze the error characteristics of this 20-bit processor in "Analysis of Logarithmic Number System Processors," Transactions on Circuits and Systems, May, 1988, 519-527.
Taylor et al. also make the fair observation that "The logarithmic number system, or LNS, has been studied for many years in a somewhat casual manner." In particular, none of these investigations has identified the specific equivalence of logarithmic computation to C-FLP computation. This equivalence has instead been denied. Moreover, there has been no prior-art processor capable of general-purpose exponential and logarithmic operations so efficient and economical that they are reasonably considered to be part of the processor's "arithmetic" along with addition, subtraction, multiplication, and division rather than expensive, inefficient library functions. Even further, despite the continuing rapid technology advances which affect the economics of storing look-up tables, all of these prior-art processor designs provide levels of precision which are clearly inadequate for general-purpose use.
In contrast, known C-FLP processors are designed for more general-purpose computation. This has come to mean that at least 20-24 significant bits or the equivalent of 6-7 significant decimal digits of precision is provided together with enough dynamic range to make overflow and underflow easily avoidable. Applications requiring more than this level of precision are common with popular computer languages such as BASIC and FORTRAN regularly providing access to more than twice this precision. There are also numerous applications within control systems and many other kinds of instrumentation using 10-, 12-, and 14-bit analog-to-digital and digital-to-analog converters wherein about 15-17 significant bits is ample precision for the carefully designed calculations which are characteristic of such applications. This is about the least precision which can claim to be widely applicable to general-purpose use even in this restricted sense.
C-FLP systems based on software implementations of numerical functions are known. However, the known software C-FLP systems can seldom provide adequate mixes of performance, function, and economy in volume-manufactured realtime microprocessor-based controllers.
The present invention targets problems which have been thought unsolvable, problems which have not been recognized, and problems which are major obstacles to practical implementation of an E/L system. Major problems not recognized as such in the prior art include areas of analysis, notation, and terminology associated with such commonly used functions as the elementary logarithms and exponentials. These areas need to be extended in a number of distinctly fundamental directions.